﻿/*
素数的位数和 
Time Limit:1000MS  Memory Limit:32768K
  
Description:
求位数为B，各位数字之和为S，又是素数的个数。
例如B=2，S=4的情况下，存在2个素数：13，31（注意该素数不能有前导0，即031不能算作3位素数）。

Input:
第一行为T，表明测试数据组数。
接下来一共T行分别为两个整数B和S，其中2<=B<=6，0<S。 
Output:
一共T行，每行对应一组B和S的解。 
Sample Input:
3
2 4
4 2
5 31
Sample Output:
2
0
379
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int flags[7][55];

static const unsigned unsigned bases[] =
{
	1U, 10U, 100U, 1000U, 10000U, 100000U, 1000000U
};
unsigned main(unsigned argc, char* argv[])
{
	unsigned t, s, b;
	vector<unsigned> vb, vs;
	cin >> t;
	vb.reserve(t + 1);
	vs.reserve(t + 1);
	while (t--)
	{
		cin >> b >> s;
		vb.push_back(b);
		vs.push_back(s);
	}
	unsigned digits = *max_element(vb.begin(), vb.end());
	unsigned maximum = bases[digits] + 1;

	vector<unsigned> primes;
	primes.push_back(2);
	primes.push_back(3);
	primes.push_back(5);

	unsigned integer = 5;
	unsigned gap = 2;
	while (integer <= maximum)//
	{
		integer += gap;
		gap = 6 - gap;
		bool is_prime = true;
		for (unsigned i = 2;
			primes[i] * primes[i] <= integer && is_prime;
			i++)
			if (0 == integer % primes[i])
				is_prime = false;
		if (is_prime)
		{
			unsigned temp = integer, sum = 0U, num = 0U;
			while (temp)
			{
				sum += temp % 10U;
				temp /= 10U;
				++num;
			}
			++flags[num][sum];
			primes.push_back(integer);
		}
	}
	//	copy(primes.begin(), primes.end(), ostream_iterator<unsigned>(cout, " "));
	for (vector<unsigned>::size_type i = 0, size = vb.size(); i < size; ++i)
		cout << flags[vb[i]][vs[i]] << endl;



	return 0;
}